class LRUCache {
public:
    LRUCache(int capacity) {
        cap=capacity;
    }
    
    int get(int key) {
        auto it=hashMap.find(key);
        if(it==hashMap.end())
            return -1;
        lru.splice(lru.begin(), lru, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it=hashMap.find(key);
        if(it != hashMap.end())
            lru.erase(it->second);
        lru.push_front(make_pair(key, value));
        hashMap[key]=lru.begin();
        if(hashMap.size() > cap)
        {
            int k=lru.rbegin()->first;
            lru.pop_back();
            hashMap.erase(k);
        }
    }

private:
    int cap;
    list<pair<int, int>>lru;
    unordered_map<int, list<pair<int,int>>::iterator >hashMap;
    
};